package nowcoder;
/**
 *
 */
import java.util.*;
public class Day23_1 {
    private class ValAndCount {
        int val;
        int count;
        ValAndCount(int val, int count) {
            this.val = val;
            this.count = count;
        }
    }
    public int getValue(int[] gifts, int n) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < gifts.length; i++) {
            map.put(gifts[i], map.getOrDefault(gifts[i], 0) + 1);
        }

        List<ValAndCount> list = new ArrayList<>();
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            list.add(new ValAndCount(entry.getKey(), entry.getValue()));
        }

        list.sort(new Comparator<ValAndCount>() {
            @Override
            public int compare(ValAndCount o1, ValAndCount o2) {
                return o2.count - o1.count;
            }
        });

        return list.get(0).count > n/2 ? list.get(0).val : 0;
    }
}